Proving Equivalences

Proving Equivalences
与 Network of Schools 的第二问答案一样。
luogu

Description

考虑到上述练习在一本普通的线性代数教科书中找到。设 $A$ 是一个 $n\times n$ 矩阵。证明以下说法是等价的:
$(\text{a})$ $A$ 是可逆的。
$(\text{b})$ $Ax=b$ 对于每个 $n\times 1$ 矩阵 $b$ 恰好有一个解。
$(\text{c})$ $Ax=b$ 对于每个 $n\times 1$ 矩阵 $b$ 是一致的。
$(\text{d})$ $Ax=0$ 仅有平凡解 $x=0$。

($a\leftrightarrow b\cap b\leftrightarrow c\cap c\leftrightarrow d\cap d\leftrightarrow a$ 和 $a\to b\cap b\to c\cap c\to d\cap d\to a$ 都能表明了这四个说法是等价，但是明显第二种简单很多。) 现在你的任务是证明 $n$ 个命题全部等价，且你的朋友已经为你做出了 $m$ 次推导（已知每次推导的内容），你至少还需要做几次推导才能完成整个证明？

Input

首先是一个正整数，表示测试用例的数量($T\le 100$) 对于每个测试用例:

• 一行，包含两个整数 $n(1\le n\le 2\times {10}^4)$ 和 $m(0\le m\le 5\times {10}^4)$：已经证明的陈述的数量和蕴含关系的数量。
• $m$ 行，每行有两个整数 $s_1$ 和 $s_2$$(1\le s_1,s_2\le n\mathrm{且}{s}_1\ne s_2)$，表示已经证明了陈述 $s_1$ 蕴含陈述 $s_2$。

Output

每个测试用例：

• 一行，包含需要证明的额外蕴含关系的最小数量，以便证明所有的陈述是等价的。

Sample Input

2
4 0
3 2
1 2
1 3

Sample Output

4
2

代码

(似乎没有平台可以提交这个代码，但是应该是对的)
ans=max(!rdu[i],!cdu[i])

#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
int n, m, dfn[N], low[N], tot, cnt, scc[N], siz[N], top, instk[N], stk[N], cdu[N], rdu[N];
vector<int> e[N];
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;

    for (int y : e[x])
    { //邻接表存图
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (instk[y])
        {
            low[x] = min(low[x], low[y]);
        }
    }

    if (dfn[x] == low[x])
    {
        int y;
        ++cnt;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        } while (y != x);
    }
}
void solve()
{
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    memset(scc, 0, sizeof scc);
    memset(siz, 0, sizeof siz);
    memset(instk, 0, sizeof instk);
    memset(stk, 0, sizeof stk);
    memset(cdu, 0, sizeof cdu);
    memset(rdu, 0, sizeof rdu);
    for (int i = 1; i <= n;i++)
        e[i].clear();
    cnt = 0, tot = 0, top = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
    {
        for (auto v : e[i])
        {
            if (scc[i] != scc[v])
            {
                cdu[scc[i]]++;
                rdu[scc[v]]++;
            }
        }
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (!cdu[i])
            cnt2++;
        if (!rdu[i])
            cnt1++;
    }
    if (cnt == 1)
        cout << "0\n";
    else
        cout << max(cnt1, cnt2) << '\n';
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
}

origin problem